package com.ry.day1129;

import java.util.HashMap;
import java.util.Map;

public class LC1081 {

    static class Solution {
        /**
         * @param stickers: a string array
         * @param target: a string
         * @return: the minimum number of stickers that you need to spell out the target
         */
        public int minStickers(String[] stickers, String target) {
            int n= stickers.length;
            int[][] counts = new int[n][26];
            for (int i = 0; i <n ; i++) {
                char[] strs = stickers[i].toCharArray();
                for (char cha : strs) {
                    counts[i][cha-'a']++;
                }
            }

            Map<String,Integer> dp = new HashMap<>();
            dp.put("",0);
            int ans = process(counts,target,dp);
            return ans==Integer.MAX_VALUE?-1: ans;
        }

        //stickers[i] 数组，当初i号贴纸的字符统计，int[][] stickers ->所有的贴纸
        //每一种贴纸都有无穷张
        //返回搞定target的最少张数
        //最少张数
        public int process(int[][] stickers,String t,Map<String,Integer> dp ){
            if(dp.containsKey(t)){
                return dp.get(t);
            }
            if(t.length() ==0) return 0;
            //target做出词频统计
            char[] target= t.toCharArray();
            int[] tcounts = new int[26];
            for (char c : target) {
                tcounts[c-'a']++;
            }

            int n= stickers.length;
            int min= Integer.MAX_VALUE;
            for (int i = 0; i <n ; i++) {
                //尝试第一张贴纸是谁
                int[] sticker = stickers[i];
                //最关键的优化（剪枝，这一步也是贪心）
                if(sticker[target[0]-'a'] >0){
                    StringBuilder sb = new StringBuilder();
                    for (int j = 0; j <26 ; j++) {
                        if(tcounts[j] >0) {
                            int nums = tcounts[j]-sticker[j];
                            for (int k = 0; k < nums; k++) {
                                sb.append((char)(j+'a'));
                            }
                        }
                    }
                    String rest = sb.toString();
                    min=Math.min(min,process(stickers,rest,dp));
                }
            }

            int ans = min+(min==Integer.MAX_VALUE?0: 1);
            dp.put(t,ans);
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.minStickers(new String[]{"with", "example", "science"},"thehat"));
        System.out.println(obj.minStickers(new String[]{"notice", "possible"},"basicbasic"));
    }

}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
1081 · 贴纸拼单词
算法
困难
通过率
56%

题目
题解9
笔记
讨论9
排名
记录
描述
给出N种不同类型的贴纸。 每个贴纸上都写有一个小写英文单词。
通过裁剪贴纸上的所有字母并重排序来拼出字符串target。
每种贴纸可以使用多次，假定每种贴纸数量无限。
拼出target最少需要多少张贴纸？如果不可能拼成，则返回-1。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


stickers的长度范围为[1, 50].
stickers仅由小写英文字母组成(没有撇号').
target的长度范围为[1, 15]，而且由小写字母组成。
在所有的测试用例中，单词是从1000个最常见的美国英文单词中任意选择的，目标单词则是由两个任意单词拼接而成。
时间限制可能比以往更有挑战性，期望的时间界是平均35毫秒50个测试样例。
样例
样例 1:

输入：
["with", "example", "science"], "thehat"
输出：
3
解释：
使用两张"with"和一张"example"，经过裁剪和重排字母，可以得到"thehat"。这也是所需要的最少贴纸数。
样例 2:

输入：
["notice", "possible"], "basicbasic"
输出：
-1
解释：
无法拼成"basicbasic"。
相关知识
学习《FLAG最新面试高频难题精讲》课程中的2.1ACM亚洲金牌选手精讲DFS（下）相关内容 ，了解更多相关知识！
标签
企业
IXL
相关题目

1270
勒索信
简单
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
267/505
已开启智能提示
发起考试
45 分 00 秒
12345678910

控制台
        历史提交

 */
